package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/'>从中序与后序遍历序列构造二叉树(Construct Binary Tree from Inorder and Postorder Traversal)</a>
 * <p>给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 *                  3
 *                 / \
 *                9  20
 *                  /  \
 *                 15   7
 *      输出：[3,9,20,null,null,15,7]
 *
 * 示例 2:
 *      输入：inorder = [-1], postorder = [-1]
 *      输出：[-1]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= preorder.length <= 3000</li>
 *         <li>postorder.length == inorder.length</li>
 *         <li>-3000 <= inorder[i], postorder[i] <= 3000</li>
 *         <li>inorder 和 postorder 都由 不同 的值组成</li>
 *         <li>postorder 中每一个值都在 inorder 中</li>
 *         <li>inorder 保证是树的中序遍历</li>
 *         <li>postorder 保证是树的后序遍历</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0105ConstructBinaryTreeFromPreorderAndInorderTraversal_M 从前序与中序遍历序列构造二叉树
 * @see LC0106ConstructBinaryTreeFromInorderAndPostorderTraversal_M 从中序与后序遍历序列构造二叉树
 * @see LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M 从前序与后序遍历序列构造二叉树
 * @since 2023/11/3 13:30
 */
public class LC0106ConstructBinaryTreeFromInorderAndPostorderTraversal_M {

    static class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            Map<Integer, Integer> inorderValue2IndexMap = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                inorderValue2IndexMap.put(inorder[i], i);
            }
            return doBuildTree(0, inorder.length - 1, inorder.length - 1, postorder, inorderValue2IndexMap);
        }

        /**
         * 构建二叉树。
         * <p>后序遍历：左->右->根</p>
         * <p>中序遍历：左->根->右</p>
         * <p>由后序遍历可以确定根节点的值，并根据根节点的值在中序遍历中找到对应位置；将中序遍历结果分为左根右三部分。
         * 根节点的值用来构建根节点，左用来构建左子树，右用来构建右子树</p>
         *
         * @param inorderLeftBoundary     构建当前树时中序遍历左边界
         * @param inorderRightBoundary    构建当前树时中序遍历右边界
         * @param rootIndexInPostorder  后序遍历根节点所在的索引位置
         * @param postorder             后序遍历集
         * @param inorderValue2IndexMap 中序遍历值与下标的映射关系
         * @return 构建后的二叉树
         */
        private TreeNode doBuildTree(
                int inorderLeftBoundary,
                int inorderRightBoundary,
                int rootIndexInPostorder,
                int[] postorder,
                Map<Integer, Integer> inorderValue2IndexMap) {
            // 结束条件
            if (inorderLeftBoundary > inorderRightBoundary) {
                return null;
            }
            // 在中序遍历中，找到根节点的位置。以该节点位置为界，分别构建左右子树
            TreeNode root = new TreeNode(postorder[rootIndexInPostorder]);
            int idx = inorderValue2IndexMap.get(root.val);
            // 构建右子树。右子树的根节点为后序遍历中，根节点的前一个节点
            root.right = doBuildTree(idx + 1, inorderRightBoundary,
                    rootIndexInPostorder - 1,
                    postorder, inorderValue2IndexMap);
            // 构建左子树。左子树的根节点为：在后序遍历中，根节点所在位置 - 右子树节点的个数(右边界 - 中序遍历根节点所在位置) - 1(前一个位置)
            root.left = doBuildTree(inorderLeftBoundary, idx - 1,
                    rootIndexInPostorder - (inorderRightBoundary - idx) - 1,
                    postorder, inorderValue2IndexMap);
            // 回溯返回根节点
            return root;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printTreeNode(solution.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3}));
        Printer.printTreeNode(solution.buildTree(new int[]{-1}, new int[]{-1}));
    }
}